import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-739-每日温度
 * @date 2025/7/1 9:50
 */
public class Solution739 {
    public static void main(String[] args) {
        int[] temperatures = new int[]{73, 74, 75, 71, 69, 72, 76, 73};
        dailyTemperatures(temperatures);
    }

    public static int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        // 维护一个自下而上的单调递减栈，里面存放temperatures的下标
        for (int i = 0; i < n; i++) {
            int temperature = temperatures[i];
            while (!stack.isEmpty() && (temperature > temperatures[stack.peek()])) {
                int ele = stack.pop();
                ans[ele] = i - ele;
            }
            stack.push(i);
        }
        return ans;
    }
}
